package leetcode_41_60;

public class isMatch_44 {
    /**
     * '?' 可以匹配任何单个字符。
     * '*' 可以匹配任意字符序列（包括空字符序列）。
     * 判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）
     *动态规划
     *25ms不够快
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch(String s, String p) {
        /*
        想法是，*对应的字符串长度是不固定的，
        还是需要动态规划
        1,如果 p[j] 是小写字母，那么 s[i] 必须也为相同的小写字母
           dp[i][j]=(s [i] 与 p [j] 相同 ) && dp[i−1][j−1]
        2,如果p[j] 是问号，那么对 s[i] 没有任何要求
           dp[i][j]=dp[i−1][j−1]
        3,如果 p[j] 是星号，那么同样对 s[i]没有任何要求，但是星号可以匹配零或任意多个小写字母
           因此状态转移方程分为两种情况，即使用或不使用这个星号
           dp[i][j]=  dp[i][j−1]   ||   dp[i−1][j]
           1) *表示空字符,则保持i不动，j-1，如果dp[i][j-1]能匹配，则dp[i][j]能匹配   aa    a*a     dp[1][2]=dp[1][1]
           2) *表示多字符,则保持j不动，i-1，如果dp[i-1][j]能匹配，则dp[i][j]能匹配   abc  a*c     dp[2][2]=dp[1][2]
           因为*表示多字符,则当前i-1加上一个字符后的i也就能匹配


           边界条件
         （0处是空字符，字符串从1开始）
           由于dp[i][j] 对应着 s 的前 i 个字符和模式 p 的前 j 个字符，因此所有的 dp[0][j] 和 dp[i][0] 都是边界条件
           1，dp[0][0]=True，即当字符串 sss 和模式 ppp 均为空时，匹配成功
           2，dp[i][0]=False，即空模式无法匹配非空字符串
           3，dp[0][j] 需要分情况讨论：因为星号才能匹配空字符串，所以只有当模式 p 的前 j 个字符均为星号时，dp[0][j] 才为真
         */
        int m = s.length(), n = p.length();
        boolean[][]  dp = new boolean[m+1][n+1];  //match[i][j]表示s的前i个字符能否被p的前j个字符匹配。
        //boolean 默认值为false
        dp[0][0] = true;
        //设置边界条件
        for (int i = 1; i <= n; ++i) {
            if (p.charAt(i - 1) == '*') {
                dp[0][i] = true;
            } else {
                break;     //只要不是从第一个开始连续的*，直接退出
            }
        }
        //这里画表格，列为 p ,行为s，演示循环，易懂
        for(int i=1; i<=m; i++) {         //s
            for(int j=1; j<=n; j++) {      //p
                if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '?') {
                    dp[i][j] =  dp[i-1][j-1];  //若s 的 i 处字符和p 的 j 处字符匹配，则match[i][j] = match[i-1][j-1]
                }
                else if(p.charAt(j-1) == '*') {        // j 处字符为*号时，进行判断
                    dp[i][j] = dp[i][j-1] || dp[i-1][j];
                }
            }
        }
        return  dp[m][n];
    }

    /**
     * 打败100%
     * 评论区解法，我稍改加上自己理解的注释
     * 1ms
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch2(String s, String p) {
        int s_len = s.length();
        int p_len = p.length();
        int s_idx = 0;       //当前s的下标
        int p_idx = 0;       //当前p的下标
        int star_idx = -1;       //离目前匹配字符最近*出现的位置
        int match = 0;      //记录目前匹配到s的第几位字符
        /*
               abcdec
               a*c
         */
        while (s_idx  < s_len) {    //对s进行遍历
            if ((p_idx < p_len) && p.charAt(p_idx) != '*' && isEqual(s.charAt(s_idx ), p.charAt(p_idx))) {  //两个字符匹配到
                s_idx ++;
                p_idx++;
            } else if ((p_idx < p_len) && p.charAt(p_idx) == '*') { //当前p字符为*
                star_idx = p_idx;    //记录*的位置
                match = s_idx ;      //记录匹配到s的第几位字符
                p_idx++; //s不动，p往下遍历,即让*号先匹配0个字符，不行再多匹配
            } else if (star_idx != -1) {      //当无法匹配，如两个字符不同，或者p已遍历完等情况时，并且之前存在*时
                p_idx = star_idx + 1;     //让p停止向下遍历，回上一个*号后边
                match++;    //s继续向下遍历
                s_idx  = match;
            } else {  //既没有*，又无法匹配，直接返回false
                return false;
            }
        }
        while (p_idx < p_len && p.charAt(p_idx) == '*') {  //s被遍历完，p的尾部还有*时，无需匹配
            p_idx++;
        }
        return p_idx == p_len; //s此时肯定被遍历完了，p被遍历完，则成功匹配，否则，不成功
    }

    public boolean isEqual(char c1, char c2) {
        return c2 == '?' || c1 == c2;
    }
}

